Search Results

Documents authored by Moser, Philip

Found 2 Possible Name Variants:

Moser, Philip

Document
DOI: 10.4230/LIPIcs.STACS.2008.1332
Pushdown Compression

Authors: Pilar Albert, Elvira Mayordomo, Philip Moser, and Sylvain Perifel

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation (Hariharan and Shankar 2006, League and Eng 2007), and in particular calls for a formulation of information-lossless stack or pushdown compressors that allows a formal analysis of their performance and a more ambitious use of the stack in XML compression, where so far it is mainly connected to parsing mechanisms. In this paper we introduce the model of pushdown compressor, based on pushdown transducers that compute a single injective function while keeping the widest generality regarding stack computation. The celebrated Lempel-Ziv algorithm LZ78 was introduced as a general purpose compression algorithm that outperforms finite-state compressors on all sequences. We compare the performance of the Lempel-Ziv algorithm with that of the pushdown compressors, or compression algorithms that can be implemented with a pushdown transducer. This comparison is made without any a priori assumption on the data's source and considering the asymptotic compression ratio for infinite sequences. We prove that Lempel-Ziv is incomparable with pushdown compressors.
Cite as

Pilar Albert, Elvira Mayordomo, Philip Moser, and Sylvain Perifel. Pushdown Compression. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 39-48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{albert_et_al:LIPIcs.STACS.2008.1332,
  author =	{Albert, Pilar and Mayordomo, Elvira and Moser, Philip and Perifel, Sylvain},
  title =	{{Pushdown Compression}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{39--48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1332},
  URN =		{urn:nbn:de:0030-drops-13327},
  doi =		{10.4230/LIPIcs.STACS.2008.1332},
  annote =	{Keywords: Finite-state compression, Lempel-Ziv algorithm, pumping-lemma, pushdown compression, XML document}
}

Moser, Philippe

Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.47
Normal Sequences with Non-Maximal Automatic Complexity

Authors: Liam Jordon and Philippe Moser

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
This paper examines Automatic Complexity, a complexity notion introduced by Shallit and Wang in 2001 [Jeffrey O. Shallit and Ming-wei Wang, 2001]. We demonstrate that there exists a normal sequence T such that I(T) = 0 and S(T) ≤ 1/2, where I(T) and S(T) are the lower and upper automatic complexity rates of T respectively. We furthermore show that there exists a Champernowne sequence C, i.e. a sequence formed by concatenating all strings of length one followed by concatenating all strings of length two and so on, such that S(C) ≤ 2/3.
Cite as

Liam Jordon and Philippe Moser. Normal Sequences with Non-Maximal Automatic Complexity. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jordon_et_al:LIPIcs.FSTTCS.2021.47,
  author =	{Jordon, Liam and Moser, Philippe},
  title =	{{Normal Sequences with Non-Maximal Automatic Complexity}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{47:1--47:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.47},
  URN =		{urn:nbn:de:0030-drops-155580},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.47},
  annote =	{Keywords: Automatic Complexity, finite-state complexity, normal sequences, Champernowne sequences, de Bruijn strings, Kolmogorov complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact